home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / os2 / pccts.zip / AUTOMATA.C < prev    next >
C/C++ Source or Header  |  1992-12-08  |  6KB  |  264 lines
  1. /* Automata conversion functions for dlg version 2
  2.  *
  3.  * Will Cohen
  4.  * 8/24/90
  5.  */
  6.  
  7. #include <stdio.h>
  8. #include "dlg.h"
  9. #ifdef MEMCHK
  10. #include "trax.h"
  11. #else
  12. extern char *malloc();
  13. extern char *calloc();
  14. #endif
  15.  
  16. #define hash_list struct _hash_list_
  17. hash_list{
  18.     hash_list *next;    /* next thing in list */
  19.     dfa_node *node;
  20. };
  21.  
  22. int    dfa_allocated = 0;    /* keeps track of number of dfa nodes */
  23. dfa_node    *dfa_array;    /* root of binary tree that stores dfa array */
  24. dfa_node    *dfa_model_node;
  25. hash_list     *dfa_hash[HASH_SIZE];    /* used to quickly find */
  26.                     /* desired dfa node */
  27.  
  28. make_dfa_model_node(width)
  29. int width;
  30. {
  31.     register int i;
  32.     dfa_model_node = (dfa_node*) malloc(sizeof(dfa_node)
  33.              + sizeof(int)*width);
  34.     dfa_model_node->left = NULL;
  35.     dfa_model_node->right = NULL;
  36.     dfa_model_node->node_no = -1; /* impossible value for real dfa node */
  37.     dfa_model_node->dfa_set = 0;
  38.     dfa_model_node->alternatives = FALSE;
  39.     dfa_model_node->done = FALSE;
  40.     dfa_model_node->nfa_states = empty;
  41.     for(i = 0; i<width; i++)
  42.         dfa_model_node->trans[i] = NIL_INDEX;
  43. }
  44.  
  45. /* finds dfa state number and returns a pointer to it */
  46. /* right now uses binary tree to store dfa nodes */
  47. dfa_node *index_dfa(i)
  48. register int i;
  49. {
  50.     dfa_node *p = dfa_array;
  51.  
  52.     if (i == NIL_INDEX)
  53.         return NULL;
  54.     while((i>1) && p){
  55.         if(i & 1)
  56.             p = p->right;
  57.         else
  58.             p = p->left;
  59.         i = i>>1;
  60.     }
  61.     return p;
  62. }
  63.  
  64.  
  65. /* adds a new dfa to the binary tree and returns a pointer to it */
  66. dfa_node *new_dfa_node(nfa_states)
  67. set nfa_states;
  68. {
  69.     dfa_node *p = dfa_array;
  70.     dfa_node *t;
  71.     int i,j;
  72.  
  73.     i = ++dfa_allocated;
  74.  
  75.     t = (dfa_node*) malloc(sizeof(nfa_node)+sizeof(int)*class_no);
  76.     *t = *dfa_model_node;
  77.     for (j=0; j<class_no; j++)
  78.         t->trans[j] = NIL_INDEX;
  79.     t->node_no = i;
  80.     t->nfa_states = set_dup(nfa_states);
  81.  
  82.     while((i>3) && p){
  83.         if(i & 1)
  84.             p = p->right;
  85.         else
  86.             p = p->left;
  87.         i = i>>1;
  88.     }
  89.     if (dfa_allocated == 1)
  90.         dfa_array = t;
  91.     else if (p != NIL_INDEX){
  92.         if (i & 1)
  93.             p->right = t;
  94.         else
  95.             p->left = t;
  96.     }
  97.     else
  98.         /* error if here */
  99.         internal_error("%s(%d): missing node on binary tree\n",
  100.             __FILE__,__LINE__);
  101.     return t;
  102. }
  103.  
  104. /* past a pointer to the start start of the nfa graph
  105.  * nfa_to_dfa convers this graph to dfa.  The function returns
  106.  * a pointer to the first dfa state.
  107.  * NOTE:  The function that prints out the table will have to figure out how
  108.  * to find the other dfa states given the first dfa_state and the number of dfa
  109.  * nodes allocated
  110.  */
  111. dfa_node *nfa_to_dfa(start)
  112. nfa_node *start;
  113. {
  114.     set x, t;
  115.     dfa_node *d_state, *trans_d_state;
  116.     int a;
  117.     int last_done;
  118.  
  119.  
  120.     if (!start) return NULL;
  121.     t = empty;
  122.     x = set_of(NFA_NO(start));
  123.     closure(&x);
  124.     /* Make x a dfa state */
  125.     d_state = dfastate(x);
  126.     last_done = DFA_NO(d_state);
  127.     
  128.     do {
  129.         /* Mark dfa state x as "done" */
  130.         d_state->done = TRUE;
  131.         last_done++; /* move forward in queue */
  132.         for (a = 0; a<class_no; a++) {
  133.             /* Build an empty set */
  134.             set_free(t);
  135.             /* Add NFA states reached by a from state b */
  136.             t = reach(d_state->nfa_states,a);
  137.             /* Were any states found? */
  138.             if (!set_nil(t)) {
  139.                 /* yes, compute closure */
  140.                 closure(&t);
  141.                 /* Make DFA state of it ... */
  142.                 trans_d_state = dfastate(t);
  143.                 /* And make transition x->t, labeled with a */
  144.                 d_state->trans[a] = DFA_NO(trans_d_state);
  145.                 d_state->alternatives = TRUE;
  146.             }
  147.         }
  148.         /* And so forth until nothing isn't done */
  149.         d_state = DFA(last_done);
  150.     } while (last_done<=dfa_allocated);
  151.     /* returns pointer to the array that holds the automaton */
  152.     return dfa_array;
  153. }
  154.  
  155. clear_hash()
  156. {
  157.     register int i;
  158.  
  159.     for(i=0; i<HASH_SIZE; i++)
  160.         dfa_hash[i] = 0;
  161. }
  162.  
  163. /* Returns a pointer to a dfa node that has the same nfa nodes in it.
  164.  * This may or maynot be a newly created node.
  165.  */
  166. dfa_node *dfastate(nfa_states)
  167. set nfa_states;        /* list of nfa states it could be */
  168. {
  169.     int bin;
  170.     hash_list *p;
  171.  
  172.     /* hash using set and see if it exists */
  173.     bin = set_hash(nfa_states,HASH_SIZE);
  174.     p = dfa_hash[bin];
  175.     while(p && !set_equ(nfa_states,(p->node)->nfa_states)){
  176.         p = p->next;
  177.     }
  178.     if(!p){
  179.         /* next state to add to hash table */
  180.         p = (hash_list*)malloc(sizeof(hash_list));
  181.         p->node = new_dfa_node(nfa_states);
  182.         p->next = dfa_hash[bin];
  183.         dfa_hash[bin] = p;
  184.     }
  185.     return (p->node);
  186. }
  187.  
  188.  
  189. /* this reach assumes the closure has been done already on set */
  190. set reach(b,a)
  191. set b;
  192. register int a;
  193. {
  194.     register unsigned int *t,*e;
  195.     nfa_node *node;
  196.     set temp;
  197.  
  198.     temp = set_of(nil);
  199.     t = e = set_pdq(b);
  200.     while (*e != nil){
  201.         node = NFA(*e);
  202.         if (set_el(a,node->label))
  203.             set_orel(NFA_NO(node->trans[0]),&temp);
  204.         e++;
  205.     }
  206.     free(t);
  207.     return temp;
  208. }
  209.  
  210. /* finds all the nodes that can be reached by epsilon transitions
  211.    from the set of a nodes and returns puts them back in set b */
  212. set closure(b)
  213. set *b;
  214. {
  215.     register nfa_node *node,*n;    /* current node being examined */
  216.     unsigned *t,*e;
  217.  
  218.     ++operation_no;
  219.     t = e = set_pdq(*b);
  220.     while (*e != nil){
  221.         node = NFA(*e);
  222.         /* mark it done */
  223.         node->nfa_set = operation_no;
  224.         if ((n=node->trans[0]) != NIL_INDEX && set_nil(node->label) &&
  225.           (n->nfa_set != operation_no)){
  226.             /* put in b */
  227.             set_orel(NFA_NO(n),b);
  228.             close1(n,operation_no,b);
  229.         }
  230.         if ((n=node->trans[1]) != NIL_INDEX &&
  231.           (n->nfa_set != operation_no)){
  232.             /* put in b */
  233.             set_orel(NFA_NO(node->trans[1]),b);
  234.             close1(n,operation_no,b);
  235.         }
  236.         e++;
  237.     }
  238.     free(t);
  239.     return *b;
  240. }
  241.  
  242. close1(node,o,b)
  243. nfa_node *node;
  244. int o;    /* marker to avoid cycles */
  245. set *b;
  246. {
  247.     register nfa_node *n;    /* current node being examined */
  248.  
  249.     /* mark it done */
  250.     node->nfa_set = o;
  251.     if ((n=node->trans[0]) != NIL_INDEX && set_nil(node->label) &&
  252.       (n->nfa_set != o)){
  253.         /* put in b */
  254.         set_orel(NFA_NO(n),b);
  255.         close1(n,o,b);
  256.     }
  257.     if ((n=node->trans[1]) != NIL_INDEX &&
  258.       (n->nfa_set != o)){
  259.         /* put in b */
  260.         set_orel(NFA_NO(node->trans[1]),b);
  261.         close1(n,o,b);
  262.     }
  263. }
  264.